Quantum computational algorithms exploit quantum mechanics to solve problemsexponentially faster than the best classical algorithms. Shor's quantumalgorithm for fast number factoring is a key example and the prime motivator inthe international effort to realise a quantum computer. However, due to thesubstantial resource requirement, to date, there have been only foursmall-scale demonstrations. Here we address this resource demand anddemonstrate a scalable version of Shor's algorithm in which the n qubit controlregister is replaced by a single qubit that is recycled n times: the totalnumber of qubits is one third of that required in the standard protocol.Encoding the work register in higher-dimensional states, we implement atwo-photon compiled algorithm to factor N=21. The algorithmic output isdistinguishable from noise, in contrast to previous demonstrations. Theseresults point to larger-scale implementations of Shor's algorithm by harnessingscalable resource reductions applicable to all physical architectures.
展开▼
